/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/search-a-2d-matrix
   @Language: C++
   @Datetime: 16-02-09 05:17
   */

// Method 1, time O(m+n)
class Solution {
public:
	/**
	 * @param matrix, a list of lists of integers
	 * @param target, an integer
	 * @return a boolean, indicate whether matrix contains target
	 * Tip: It fits for ordered row and ordered col, and do not
	 *      need first of row is larger than last of previous row
	 */
	bool searchMatrix(vector<vector<int> > &matrix, int target) {
		// write your code here
		if (matrix.size()<1 || matrix[0].size()<1) return false;
		for(int i=matrix.size()-1,j=0; i>=0 && j<matrix[i].size();)
			if (matrix[i][j]==target) return true;
			else if (matrix[i][j]>target) --i;
			else ++j;
		return false;
	}
};

// Method 2, time O(log(m*n))
class Solution {
public:
	/**
	 * @param matrix, a list of lists of integers
	 * @param target, an integer
	 * @return a boolean, indicate whether matrix contains target
	 * Tip: The first num of each row is larger than last num of previous row
	 *      Thus, this matrix can be converted to an ordered array,
	 *      which has row*col elements.
	 */
	bool searchMatrix(vector<vector<int> > &matrix, int target) {
		// write your code here
		if (matrix.size()<1 || matrix[0].size()<1) return false;
		int row=matrix.size(), col=matrix[0].size();
		for(int i=0,j=row*col,mid; i<j;){
			mid=(j-i)/2+i;
			if(matrix[mid/col][mid%col]==target) return true;
			if(matrix[mid/col][mid%col]>target) j=mid;
			else i=mid+1;
		}
		return false;
	}
};
